using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;


namespace Rogue
{


    // A dungeon is made of connected rooms (AA rectangles). Most of this code is to connect them and lay them out with corridors.
    #region rooms
        
    using RoomSet = Dictionary<Room, int>;

    // Room vs. Map could be factored out into a common class, like he does in the tutorial...
    class Room
    {
        public Rectangle _Bounds;
        public RoomSet m_SetOfRoomsImIn;    // only used in the corridor step... the int arg isn't used.

        public Room(Rectangle a_Bounds)
        {
            _Bounds = a_Bounds;
        }

        public void ClearPerim(MapGenerator a_mapGen, string a_Mat, Rectangle a_Rect)
        {
            for (int x = a_Rect.Left; x < a_Rect.Right; ++x)
            {
                for (int y = a_Rect.Top; y < a_Rect.Bottom; ++y)
                {
                    if (x == a_Rect.Left || x == a_Rect.Right - 1 ||
                        y == a_Rect.Top  || y == a_Rect.Bottom - 1)
                    {
                        a_mapGen.SetTerrain(x, y, a_Mat);
                    }
                }
            }
        }

        public void ClearSpace(MapGenerator a_mapGen, string floorMat, string wallMat)
        {
            if (floorMat.Length != 0)
            {
                for (int x = _Bounds.Left; x < _Bounds.Right; ++x)
                {
                    for (int y = _Bounds.Top; y < _Bounds.Bottom; ++y)
                    {
                        a_mapGen.SetTerrain(x, y, floorMat);
                    }
                }
            }

            if (wallMat.Length != 0)
            {
                ClearPerim(a_mapGen, wallMat, _Bounds);
            }
        }

        public Point RandomPoint()
        {
            return new Point(_Bounds.Left + Random.Instance.Next(_Bounds.Width),
                             _Bounds.Top + Random.Instance.Next(_Bounds.Height));
        }


    };
    #endregion
    
    public class MapGenerator
    {
        GameMap     m_Map;

        public MapGenerator(GameMap a_Map)
        {
            m_Map = a_Map;
            _rooms = new List<Room>();
        }

        // Split to a new class?
        #region forest generation. 
        public class ForestParams
        {
            public float grassChance = 0.3f;
            public float darkGrassChance = 0.25f;
            // public float treeChance = // 1-the above

            public int numSmoothings = 3;
            public int maxOpenOf9ForSolid = 4;
            public int minOpenOf25ForSolid = 22;

            public int width = 30;
            public int height = 60;

            public bool hasWon = false;
        }

        public void Run(ForestParams p)
        {
            m_Map.m_MapData = new MapCell[p.width, p.height];

            m_Map.SetAllMapped(false);
            m_Map.m_ShadowColor = new Vector3(0.5f, 0.5f, 0.6f);

            RandomizeForest(p);

            for (int i = 0; i < p.numSmoothings; ++i )
                SmoothingPass(p);

            SaplingPass(p);

            ConnectHoles(p);

            Entity hero = m_Map.GetHero();
            hero.Position = FindFreeSpot(new Point(7, 7), new Point(15, 15));

            exit = BuildHouse(hero);

            if (!p.hasWon)
            {
                hero.OnMove += new Entity.MoveHandler(hero_OnMoveToDoor);

                string msg = "This is you! (The @ symbol).\n\n" + 
                    "Move around using the numpad:\n" + 
                    "8, 2, 4, and 6 for up, down, left, and right,\n" +
                    "and 7, 9, 1 and 3 to move diagonally.\n\n";

                TutWindow.Instance.Show("movement", msg, 3.0f, hero);
            }
            else
            {
                PlaceNEntities<Bunny>(5);
                exit.IsAlive = false;

                ConsoleWindow.Instance.AddMessage("You defeated the Goblin King! The world is once again at peace. You retire to your bunny farm.", Color.Yellow);
            }
        }

        // temp variables used by the mission. This is kind of a poopy place for the mission/tutorials.
        // Should be factored out into a mission instance?
        Door exit = null;

        void hero_OnMoveToDoor(Entity.MoveArgs e)
        {
            Entity hero = m_Map.GetHero();

            if (hero.X > exit.X - 4 && !m_bShowedTutsTut)
            {
                m_bShowedTutsTut = true;

                string msg = "This is the tutorials screen.\n\n" +
                    "To review old messages, press the < and > buttons in the upper right (or on the keyboard). To dismiss a tutorial, press X.\n\n" +
                    "Tutorials will go away automatically once you move around. To hide or show tutorials alltogether, press T. " +
                    "If you've hidden the tutorial screen, a little notification shows up in the upper right when you have an unread tutorial.";
                TutWindow.Instance.Show("Tutorials", msg, 3.0f);
            }

            if (hero.X > exit.X - 3)
            {
                TutWindow.Instance.Show("Attacking", "You attack things by walking into them.\n\nBreak out of your hut by walking into your door.", 1.0f, exit);

                exit.OnDamage += new Entity.DamageHandler(exit_OnPlayerBump);

                hero.OnMove -= hero_OnMoveToDoor;
            }
        }

        void exit_OnPlayerBump(Entity.DamageArgs e)
        {
            string msg = "This is the Enemy window, which shows the health of different parts of the enemy you're fighting." + 
                "(press 'E' to show or hide it, or click on an enemy in the world).\n\n" + 
                "To attack a specific part of an enemy, click on that part or press the matching number key for that part.\n\n" + 
                "Most enemies have a weakness, or can be easily disabled by hitting certain parts of their body.\n\n" + 
                "To attack an enemy faster (if you don't care where you hit them), just keep bumping into them.";

            TutWindow.Instance.Show("The Enemy Window", msg, 10.0f, DetailWindow.EnemyWindow);
            DetailWindow.EnemyWindow.Focus(exit, false);

            exit.OnDamage -= exit_OnPlayerBump;

            exit.OnDeath += new Entity.DeathHandler(exit_OnDeath);
        }

        void exit_OnDeath(Entity.DeathArgs e)
        {
            string msg = "Congrats, you just solved a problem with violence, winning your first fight against a helpless door.\n\n" + 
                "You can see a log of what's happening in a fight, down here in the Console.\n\n" + 
                "Take a step outside!";

            Tutorial t = TutWindow.Instance.Show("The Console Window", msg, 10.0f, ConsoleWindow.Instance);
            t.m_Position = new Point(TutWindow.Instance.Position.X - 20, 450);

            exit.OnDeath -= exit_OnDeath;

            Entity hero = m_Map.GetHero();
            hero.OnMove += new Entity.MoveHandler(hero_OnMoveOutside);
        }

        int numMovesSinceLeaving = 0;
        bool m_bShowedMissionTut = false;
        bool m_bShowedTutsTut = false;
        
        void hero_OnMoveOutside(Entity.MoveArgs e)
        {
            Entity hero = m_Map.GetHero();

            if (hero.X > exit.X && numMovesSinceLeaving == 0)
            {
                numMovesSinceLeaving = 1;
            }

            if (numMovesSinceLeaving == 1)
            {
                DetailWindow.EnemyWindow.Focus(null, true);

                string msg = "You can only see what's near you. This is represented by brightness on the map, like a fog of war. Areas you've never seen are black.\n\n" + 
                    "If you've seen an area before but can't see it now, it will show up greyed out (because you remember the terrain, " + 
                    "but you won't know what enemies are there). Notice how as you move around, trees cast shadows, meaning you can't see what's behind them.";
                TutWindow.Instance.Show("Visibility", msg, 10.0f);

                numMovesSinceLeaving = 2;
            }

            // wait until we're outside to start counting
            if (numMovesSinceLeaving > 1)       // wait until we're outside before counting
            {
                numMovesSinceLeaving++;
            }

            if (numMovesSinceLeaving >= 1 && !m_bShowedMissionTut)
            {
                string msg = "To talk to friendly people (eg. to get a mission from a friendly old villager), bump into them.";
                TutWindow.Instance.Show("Talking", msg, 3.0f);
                m_bShowedMissionTut = true;
            }

            if (m_bShowedMissionTut && numMovesSinceLeaving > 8)
            {
                hero.OnMove -= hero_OnMoveOutside;

                missionGiver = new Human("Old dude");
                m_Map.m_EntityTable.Add(missionGiver.Name, missionGiver);
                missionGiver.Position = FindFreeSpot(hero.Position, 10);

                RogueGame.Instance.CurMission = new Mission(missionGiver, "Hey!", "Find the dungeon to the south.\nIt has goblins or something.\nWatch out for wolves!");
                missionGiver.OnPlayerBump += new Entity.PlayerBumpHandler(giver_OnGetMission);

                RogueGame.Instance.CurMission.AddDelayedCall(0.5f, MissionStartMessage);
            }
        }

        void MissionStartMessage()
        {
            ConsoleWindow.Instance.AddMessage("Go talk to the sad-looking old dude who's shouting at you!", Color.Yellow);
        }

        Human missionGiver = null;
        Stairs m_StairsForTut = null;

        void giver_OnGetMission(Entity.BumpArgs e)
        {
            PlaceNEntities<Wolf>(5);

            Stairs stairs = new Stairs();
            stairs.Position = FindFreeSpot(new Point(m_Map.Width - 15, m_Map.Height - 15), new Point(m_Map.Width, m_Map.Height));
            missionGiver.OnPlayerBump -= new Entity.PlayerBumpHandler(giver_OnGetMission);

            stairs.OnPlayerBump += new Entity.PlayerBumpHandler(Mission.stairs_OnPlayerBump);
            stairs.OnPlayerBump += new Entity.PlayerBumpHandler(stairs_OnPlayerBump);

            Entity hero = m_Map.GetHero();
            hero.OnMove += new Entity.MoveHandler(hero_OnMoveStairsTut);
            hero.BodyRoot.OnSubPartHealthChange += new BodyPart.HealthChangeHandler(hero_HealingTut);
            
            m_StairsForTut = stairs;

            RogueGame.Instance.CurMission.AddDelayedCall(3.0f, CombatStartTut);    
        }

        void hero_HealingTut(BodyPart a_Part, BodyPart.HealthChangeType a_ChangeType, int a_DeltaHealth)
        {
            Entity hero = m_Map.GetHero();

            // wait until we're healing with no enemies around
            if (a_DeltaHealth > 0 && (DetailWindow.EnemyWindow.FocusEntity == null || !DetailWindow.EnemyWindow.FocusEntity.IsAlive))
            {
                bool nearbyEnemies = false;
                foreach (Entity enemy in Entity.Collector.GetAllWithin<Entity>(hero.Position, 20))
                {
                    if (m_Map.LightCaster.IsVisible(enemy.Position) && enemy.IsAlive &&
                        (enemy.GetType() == typeof(Wolf) || enemy.GetType() == typeof(Goblin)) )
                    {
                        nearbyEnemies = true;
                    }
                }

                if (!nearbyEnemies)
                {
                    string msg = "When you're hurt, you automatically heal over time. You can see yourself heal with the Hero window open (press W).\n\n" +
                        "When a body part takes enough damage, you will lose it. If you lose legs, you will move slowly. If you lose arms, you can't use them to attack. If your torso or head is destroyed, you die (this is true for enemies too!).\n\n" + 
                        "You can stand still and heal (and let time pass) by holding 5 on the numpad. This can also be a useful combat tactic, if you want to wait briefly.";

                    Tutorial t = TutWindow.Instance.Show("Healing", msg, 3.0f, DetailWindow.HeroWindow);

                    if (TutWindow.Instance.GetActiveTut() == t && TutWindow.Instance.IsActive)
                    {
                        DetailWindow.HeroWindow.Focus(hero, true);
                    }

                    hero.BodyRoot.OnSubPartHealthChange -= hero_HealingTut;
                }
            }
        }

        void hero_OnMoveStairsTut(Entity.MoveArgs e)
        {
            if (m_StairsForTut != null && RogueGame.Instance.Map.LightCaster.IsVisible(m_StairsForTut.Position))
            {
                TutWindow.Instance.Show("Stairs", "Stairs instantly move you to another part of the world (eg. in or out of a dungeon). Enemies can't use them.", 3.0f);

                Entity hero = m_Map.GetHero();
                hero.OnMove -= hero_OnMoveStairsTut;
            }
        }

        void CombatStartTut()
        {
            Entity hero = m_Map.GetHero();
            hero.OnMove += new Entity.MoveHandler(hero_OnMoveWithMission);
        }

        bool m_bShowedTurns = false;

        void hero_OnMoveWithMission(Entity.MoveArgs e)
        {
            Entity hero = m_Map.GetHero();
            
            if (!m_bShowedTurns)
            {
                string msg = "This game is turn-based, which means after all the creatures in the world have moved, the game pauses for you decide what to do.\n\n" +
                    "If you press a button before the other creatures are done their turns, the game instantly jumps ahead to show your next turn. " + 
                    "So the other creatures still finish their turns, but you don't watch them as they happen.";
                TutWindow.Instance.Show("Turns", msg, 5.0f);
                m_bShowedTurns = true;

                hero.OnMove -= hero_OnMoveWithMission;
            }
        }

        void stairs_OnPlayerBump(Entity.BumpArgs e)
        {
            if (RogueGame.Instance.CurMission != null)
                RogueGame.Instance.CurMission.CleanupLabels(); // clean up the label and such. Should we get a new mission here?
        }

        void RandomizeForest(ForestParams p)
        {
            for (int x = 0; x < m_Map.m_MapData.GetLength(0); x++)
            {
                for (int y = 0; y < m_Map.m_MapData.GetLength(1); y++)
                {
                    float picker = Random.Instance.Next();

                    if (picker < p.grassChance)
                    {
                        m_Map.SetTerrain(x, y, "terrain.grass");
                        continue;
                    }
                    picker -= p.grassChance;
                    if (picker < p.darkGrassChance)
                    {
                        m_Map.SetTerrain(x, y, "terrain.darkgrass");
                        continue;
                    }
                    
                    m_Map.SetTerrain(x, y, "terrain.tree");
                    continue;
                }
            }
        }

        void SmoothingPass(ForestParams p)
        {
            // we need to defer all the sets so we aren't reading data as it's modified.
            // We could make a copy of the map's data and work (or read) with that, 
            // but the problem with that is all the functions to set the map data are part of the map class.
            Dictionary<Point, string> deferSets = new Dictionary<Point, string>();

            // http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels

            // We could also use this as a smoothing pass on other-algorithm generated dungeons...

            for (int x = 0; x < m_Map.m_MapData.GetLength(0); x++)
            {
                for (int y = 0; y < m_Map.m_MapData.GetLength(1); y++)
                {
                    int numOf9Open = GetNum(IsPassable, Get9Neighbors(x, y)) + (GetNum(m_Map.IsInBounds, Get25Neighbors(x, y)) - 25);
                    int numOf25Open = GetNum(IsPassable, Get25Neighbors(x, y));
                    if (numOf9Open <= p.maxOpenOf9ForSolid || numOf25Open >= p.minOpenOf25ForSolid)
                    {
                        if (m_Map.m_MapData[x,y].TerrainDefinition != "terrain.tree")
                            deferSets.Add(new Point(x, y), "terrain.tree");
                    }
                    else if (m_Map.m_MapData[x,y].TerrainDefinition == "terrain.tree")  // only if it needs to change...
                    {
                        float picker = Random.Instance.Next();

                        if (picker < p.grassChance)
                            deferSets.Add(new Point(x, y), "terrain.grass");
                        else
                            deferSets.Add(new Point(x, y), "terrain.darkgrass");
                    }
                }
            }

            foreach (KeyValuePair<Point, string> kvp in deferSets)
            {
                m_Map.SetTerrain(kvp.Key.X, kvp.Key.Y, kvp.Value);
            }
        }

        void SaplingPass(ForestParams p)
        {
            for (int x = 0; x < m_Map.m_MapData.GetLength(0); x++)
            {
                for (int y = 0; y < m_Map.m_MapData.GetLength(1); y++)
                {
                    if (m_Map.m_MapData[x, y].TerrainDefinition == "terrain.tree")
                    {
                        int numOf9Open = GetNum(IsPassable, Get9Neighbors(x, y));
                        int numOf25Open = GetNum(IsPassable, Get25Neighbors(x, y));

                        if (5 + numOf9Open > Random.Instance.Next(24))
                        {
                            m_Map.SetTerrain(x, y, "terrain.sapling");
                        }

                        if (10 + numOf25Open > Random.Instance.Next(55))
                        {
                            m_Map.SetTerrain(x, y, "terrain.deadtree");
                        }
                    }                    
                }
            }
        }

        void ConnectHoles(ForestParams forParams)
        {
            // first, find each connected area as a set
            bool[,] expandedFrom = new bool[m_Map.Width, m_Map.Height];
            expandedFrom.Initialize();

            Dictionary<Point, List<Point>> pointToSet = new Dictionary<Point, List<Point>>();
            List<List<Point>> uniqueSets = new List<List<Point>>();

            Stack<Point> stack = new Stack<Point>();  // things to look at
            for (int x = 0; x < m_Map.m_MapData.GetLength(0); x++)
            {
                for (int y = 0; y < m_Map.m_MapData.GetLength(1); y++)
                {
                    if (IsPassable(x, y))
                        stack.Push(new Point(x, y));
                }
            }

            while (stack.Count > 0)
            {
                Point parent = stack.Pop();

                if (!IsPassable(parent) || expandedFrom[parent.X, parent.Y])    // solid or already visited 
                    continue;

                expandedFrom[parent.X, parent.Y] = true;

                List<Point> set = null;
                if (!pointToSet.TryGetValue(parent, out set))
                {
                    set = new List<Point>();
                    uniqueSets.Add(set);

                    set.Add(parent);
                    pointToSet[parent] = set;
                }                

                foreach (Point nearby in Get8Neighbors(parent.X, parent.Y))
                {
                    if (!IsPassable(nearby) || expandedFrom[nearby.X, nearby.Y])
                        continue;

                    pointToSet[nearby] = set;   // don't visit it again
                    set.Add(nearby);      // it's part of this set
                    
                    stack.Push(nearby);     // explore further from here later
                }
            }

            List<Point> longest = null;
            foreach (List<Point> set in uniqueSets)
            {
                if (longest == null || set.Count > longest.Count)
                    longest = set;
            }

            // connect the small holes to the larger areas.
            // TODO: kruskal again? This is kind of hacky :<
            // And isn't even guaranteed to connect everything!
            foreach (List<Point> set in uniqueSets)
            {
                if (set == longest)
                    continue;

                CorridorParams cp;
                cp.maxAng = 0.5f;
                cp.angStep = 0.05f;
                cp.noise = 0.4f;

                Point start = set[Random.Instance.Next(set.Count)];
                Point end = longest[Random.Instance.Next(longest.Count)];
                foreach (Point p in ScrewyTunnel(m_Map, cp, start, end, false))
                {
                    // yay, we broke out to another set
                    if (pointToSet.ContainsKey(p) && pointToSet[p] != set)
                        break;

                    if (Random.Instance.Next() < forParams.grassChance)
                        m_Map.SetTerrain(p.X, p.Y, "terrain.grass");
                    else
                        m_Map.SetTerrain(p.X, p.Y, "terrain.darkgrass");
                }
            }
        }

        Door BuildHouse(Entity Hero)
        {
            Rectangle rect = new Rectangle(Hero.Position.X - 1, Hero.Position.Y - 1, 7, 5);
            Room newRoom = new Room(rect);
            newRoom.ClearSpace(this, "terrain.floor.dirt", "terrain.woodwall");
            Rectangle expanded = rect;
            expanded.Inflate(1, 1);
            newRoom.ClearPerim(this, "terrain.darkgrass", expanded);
            expanded.Inflate(1, 1);
            newRoom.ClearPerim(this, "terrain.grass", expanded);

            SetTerrain(Hero.Position.X, Hero.Position.Y, "terrain.bed");

            Point doorPos = new Point(Hero.Position.X + rect.Width-2, Hero.Position.Y + 1);
            Door door = new Door("hut door");
            SetTerrain(doorPos.X, doorPos.Y, "terrain.floor.dirt");
            door.Position = doorPos;
            return door;
        }

        Point FindFreeSpot()
        {
            return FindFreeSpot(Point.Zero, new Point(m_Map.Width, m_Map.Height));
        }

        Point FindFreeSpot(Point a, int radius)
        {
            return FindFreeSpot(new Point(a.X - radius, a.Y - radius),
                                new Point(a.X + radius, a.Y + radius));
        }

        Point FindFreeSpot(Point a_Min, Point a_Max)
        {
            // try to set the position of each one a few times...
            for (int growArea = 0; growArea < 5; growArea++)
            {
                for (int tries = 0; tries < 100; tries++)
                {
                    int x = Random.Instance.Next(a_Min.X, a_Max.X);
                    int y = Random.Instance.Next(a_Min.Y, a_Max.Y);

                    if (!m_Map.BlocksActor(x, y) && !m_Map.LightCaster.IsVisible(new Point(x, y)))
                    {
                        return new Point(x, y);
                    }
                }

                a_Min.X -= 10;
                a_Min.Y -= 10;
                a_Max.X += 10;
                a_Max.Y += 10;
            }

            throw new ArgumentException("Can't find free spot :<");
        }

        private void PlaceNEntities<T>(int a_Num) where T : Entity, new()
        {
            for (int w = 0; w < a_Num; ++w)
            {
                T newEntity = new T();
                newEntity.Position = FindFreeSpot();
                newEntity.NextThink = Random.Instance.Next(5) * 10 + Timeline.Instance.CurrentTime;
                Timeline.Instance.Add(newEntity);
            }
        }

        #endregion



        public class DungeonParams
        {
            public int width = 40;
            public int height = 40;

            public float goblinDensity;

            public float roomDensity;      // fraction of dungeon area filled with room area
            public int roomMinWidth;
            public int roomMaxWidth;
            public int roomMinHeight;
            public int roomMaxHeight;

            public float extraCorridorChance;  // chance of corridors that aren't necessary for a minimal connection

            public float deadEndChance;
            public int deadEndMinLength;
            public int deadEndMaxLength;

            public float doorChance;

            public CorridorParams roomToRoomCorr;
            public CorridorParams deadEndCorr;
        };

        public struct CorridorParams
        {
            public float maxAng;   // how far away a corridor can deflect from its target
            public float angStep;  // how fast that angle changes
            public float noise;    // when we approach a target, the chance we take the same axis as the last step
        };

        List<Room> _rooms;

        public void Run(DungeonParams p)
        {
            m_Map.m_MapData = new MapCell[p.width, p.height];

            m_Map.SetAllMapped(false);
            m_Map.SetAllTerrain("terrain.granite");
            m_Map.m_ShadowColor = new Vector3(0.07f, 0.07f, 0.15f);

            AddRooms(p);
            ConnectAllRooms(p);
            AddDeadEnds(p);
            AddEntities(p);

            _rooms.Clear();     // clear temporary data
        }

        // complicate this?
        public void SetTerrain(int a_X, int a_Y, string a_Def)
        {
            TerrainDef def = TerrainDatabase.Instance.GetDefinition(a_Def);

            m_Map.m_MapData[a_X, a_Y].TerrainDefinition = a_Def;

            m_Map.m_MapData[a_X, a_Y].TerrainUpTile = (char)def.UpTile;
            m_Map.m_MapData[a_X, a_Y].TerrainUpColor = new Color(def.UpColor);

            m_Map.m_MapData[a_X, a_Y].TerrainForegroundTile = (char)def.ForegroundTile;
            m_Map.m_MapData[a_X, a_Y].TerrainForeColor = new Color(def.ForeColor);

            m_Map.m_MapData[a_X, a_Y].TerrainBackgroundTile = (char)def.BackgroundTile;
            m_Map.m_MapData[a_X, a_Y].TerrainBackColor = new Color(def.BackColor);

            m_Map.m_MapData[a_X, a_Y].BlocksLight = def.BlocksLight;
            m_Map.m_MapData[a_X, a_Y].BlocksActor = def.BlocksActor;
        }

        void AddRooms(DungeonParams p)
        {
            int totalArea = m_Map.Width * m_Map.Height;
            int avgRoomArea = (p.roomMinWidth + p.roomMaxWidth) / 2 * (p.roomMinHeight + p.roomMaxWidth) / 2;
            int totalRoomArea = (int) (totalArea * p.roomDensity);
            int numRooms = Math.Max(1, totalRoomArea / avgRoomArea);

            // optimization todo: spatial indexing for room-room overlap compares
            Random r = Random.Instance;

            for (int i = 0; i < numRooms; i++)
            {
                int w = r.Next(p.roomMinWidth, p.roomMaxWidth);
                int h = r.Next(p.roomMinHeight, p.roomMaxWidth);

                // try 5 times to find a random spot that doesn't overlap an existing room. 
                // If we've failed that many times in a row, assume the map is too dense...
                Rectangle bounds = new Rectangle(m_Map.Width/2, m_Map.Height/2, 1, 1);
                for (int tries = 0; tries < 5; tries++ )
                {
                    int x = r.Next(1, m_Map.Width - w - 1);      // -1 to leave a border for the world
                    int y = r.Next(1, m_Map.Height - h - 1);
                    bounds = new Rectangle(x, y, w, h);

                    bool overlap = false;
                    foreach (Room room in _rooms)
                    {
                        if (room._Bounds.Intersects(bounds))
                        {
                            overlap = true;
                            break;
                        }
                    }

                    if (!overlap)
                    {
                        Room newRoom = new Room(bounds);
                        newRoom.ClearSpace(this, "terrain.floor.tilegranite", "");
                        _rooms.Add(newRoom);
                    }
                }
            }
        }

        // the distance between the middle of two rooms
        float DistanceSq(Room a, Room b)
        {
            Vector2 dist = new Vector2( (a._Bounds.X + a._Bounds.Width)/2 - (b._Bounds.X + b._Bounds.Width)/2, 
                                        (a._Bounds.Y + a._Bounds.Height)/2 - (b._Bounds.Y + b._Bounds.Height)/2);
            return dist.LengthSquared();
        }

        // two rooms
        struct RoomPair
        {
            public RoomPair(Room a_RoomA, Room a_RoomB)
            {
                _roomA = a_RoomA;
                _roomB = a_RoomB;
            }

            public Room _roomA;
            public Room _roomB;
        };

        // the squared distance between two rooms. This is kind of retarded, but keys in a Sorted collection need to be 'unique',
        // so this is a hack that lets us store duplicates (ie treating it as a multimap).
        struct UniqueDistComparer : IComparer<int>
        {
            public int Compare(int a, int b)
            {
                if (a < b)
                    return -1;
                else
                    return 1;
            }
        };

        void ConnectAllRooms(DungeonParams p)
        {
            // kruskal's algorithm for minimum spanning trees: http://en.wikipedia.org/wiki/Minimum_spanning_tree

            // initialize a set for every room
            foreach (Room a in _rooms)
            {
                a.m_SetOfRoomsImIn = new RoomSet();
                a.m_SetOfRoomsImIn.Add(a, 0);
            }

            // find out the distances between all the pairs of rooms. This is the bottleneck...
            // although we don't generate O(n2) graph nodes, there are that many distance checks.
            int areaPerRoom = (m_Map.Height * m_Map.Width) / _rooms.Count;
            int maxSqDistBetweenRooms = (int) (2 * areaPerRoom);  // the worst case

            SortedDictionary<int, RoomPair> allDistances = new SortedDictionary<int, RoomPair>(new UniqueDistComparer());
            foreach (Room a in _rooms)
            {
                foreach(Room b in _rooms)
                {
                    if (a.GetHashCode() < b.GetHashCode())      // avoid dupes in the tree...
                        continue;

                    int distance = (int) DistanceSq(a, b);

                    if (distance < maxSqDistBetweenRooms)               // these won't be the closest dudes for sure, they're so far apart
                        allDistances.Add(distance, new RoomPair(a, b));
                }
            }

            // greedily merge the sets, merging closest rooms first
            foreach (KeyValuePair<int, RoomPair> distPair in allDistances)
            {
                Room roomA = distPair.Value._roomA;
                Room roomB = distPair.Value._roomB;
                RoomSet setA = roomA.m_SetOfRoomsImIn;
                RoomSet setB = roomB.m_SetOfRoomsImIn;

                bool mergeSets = (setA != setB);
                bool extraCorridor = (DistanceSq(roomA, roomB) > maxSqDistBetweenRooms/4 && 
                                      p.extraCorridorChance >= Random.Instance.Next());

                bool carveCorridor = mergeSets || extraCorridor;

                if (!mergeSets && !carveCorridor)
                    continue;

                if (mergeSets)
                {
                    foreach (Room r in setA.Keys)
                    {
                        r.m_SetOfRoomsImIn = setB;
                        setB.Add(r, 0);
                    }
                }
                
                if (carveCorridor)
                    ConnectRooms(p, distPair.Value._roomA, distPair.Value._roomB, extraCorridor);
            }
        }


        IEnumerable<Point> ScrewyTunnel(GameMap a_map, 
                                        CorridorParams cp,
                                        Point a_From, Point a_To, 
                                        bool a_DeadEnd)
        {
            Point iter = a_From;

            Rectangle shrunkMapBounds = m_Map.Bounds();
            shrunkMapBounds.Inflate(-1, -1);

            bool phaseIncreasing = true;    // we bounce the phase back and force
            float rand = Random.Instance.Next();
            double phase = cp.maxAng * (2 * rand - 1);

            while (iter != a_To)
            {
                int diffX = a_To.X - iter.X;
                int diffY = a_To.Y - iter.Y;

                Point onMap = iter;

                // if we're too close to one of the targets, we want to avoid orbiting it
                int distToFrom = Math.Abs(a_From.X - iter.X) + Math.Abs(a_From.Y - iter.Y);
                int distToTo = Math.Abs(a_To.X - iter.X) + Math.Abs(a_To.Y - iter.Y);
                bool doTwist = a_DeadEnd || (distToFrom > 5 && distToTo > 5);

                // we're far enough from the target, screw with it. This is kind of wacky...
                // we get the direction we're travelling and randomly offset it.
                if (doTwist && cp.angStep > 0.01f && cp.maxAng > 0.1f)
                {
                    Matrix rotMat = Matrix.CreateRotationZ((float)phase);
                    Vector2 diffVec = Vector2.Transform(new Vector2(diffX, diffY), rotMat);
                    diffX = (int)diffVec.X;
                    diffY = (int)diffVec.Y;
                }

                bool movetowardsX;
                if (doTwist && Random.Instance.Next() < cp.noise)
                {
                    movetowardsX = Random.Instance.Next() > 0.5f;
                }
                else
                {
                    // when we get close, go in straight lines.
                    movetowardsX = Math.Abs(diffX) > Math.Abs(diffY);
                }

                // pick whether we want to head towards X or Y
                if (movetowardsX)
                {
                    iter.X += Math.Sign(diffX);
                }
                else
                {
                    iter.Y += Math.Sign(diffY);
                }

                if (phaseIncreasing)
                {
                    phase += cp.angStep;
                    if (phase > cp.maxAng)
                        phaseIncreasing = false;
                }
                else
                {
                    phase -= cp.angStep;
                    if (phase < -cp.maxAng)
                        phaseIncreasing = true;
                }

                // if we've stepped off the map, get back on it
                if (!shrunkMapBounds.Contains(iter))
                {
                    if (a_DeadEnd)  // unless we're a dead end, then just give up
                    {
                        yield break;
                    }

                    iter = onMap;
                    if (iter.X < 1)
                        ++iter.X;
                    else if (iter.X >= m_Map.Width - 1)
                        --iter.X;

                    else if (iter.Y < 1)
                        ++iter.Y;
                    else if (iter.Y >= m_Map.Height - 1)
                        --iter.Y;
                }

                yield return iter;
            }
        }

        
        // "can cancel" means it's not neccesary for pathfinding the level, we can cut it off early
        void ConnectRooms(DungeonParams p, Room a, Room b, bool a_CanCancelTunnel)
        {
            // TODO: complicate this so it wanders nicer. Some kind of smoothed noise...
            // also have corridors enter rooms always at 90%, so they don't leave a weird parallel section.
            // protip: make an expanded room bounds, and once we enter that shell (2 tiles wide), head straight
            // for the middle of the room? 
            Point start = new Point(a._Bounds.Left + a._Bounds.Width / 2, a._Bounds.Top + a._Bounds.Height / 2);
            Point target = new Point(b._Bounds.Left + b._Bounds.Width / 2, b._Bounds.Top + b._Bounds.Height / 2);


            Rectangle fatABounds = a._Bounds;
            fatABounds.Inflate(1, 1); 
            Rectangle fatBBounds = b._Bounds;
            fatBBounds.Inflate(1, 1);

            // we have to wait until we've carved the tunnel to put down doors,
            // because later carving might invalidate an earlier door point
            List<Point> doorCandidates = new List<Point>();

            foreach (Point iter in ScrewyTunnel(m_Map, p.roomToRoomCorr, start, target, false))
            {
                if (a._Bounds.Contains(iter))       // just started
                    continue;

                if (b._Bounds.Contains(iter))       // done carving
                    break;

                SetTerrain(iter.X, iter.Y, "terrain.floor.tilegranite");

                doorCandidates.Add(iter);

                if (a_CanCancelTunnel)
                {
                    // don't mess up door placement with random tunnels
                    if (GetNum(HasEntityAt<Door>, Get8Neighbors(iter.X, iter.Y)) > 0)
                        break;

                    // we hit another tunnel, stop
                    if (GetNum(IsPassable, Get4Neighbors(iter.X, iter.Y)) >= 3)
                        break;
                }
            }

            Point startDoor = start;
            Point endDoor = start;
            bool haveStartDoor = false;
            bool haveEndDoor = false;
            foreach (Point doorP in doorCandidates)
            {
                // two adjacent doors is silly if they're blocking the same corridor
                bool solidLeftAndRight = !IsPassable(doorP.X - 1, doorP.Y) && !IsPassable(doorP.X + 1, doorP.Y) &&
                                         !HasEntityAt<Door>(doorP.X, doorP.Y - 1) && !HasEntityAt<Door>(doorP.X, doorP.Y + 1);

                bool solidTopAndBottom = !IsPassable(doorP.X, doorP.Y - 1) && !IsPassable(doorP.X, doorP.Y + 1) &&
                                         !HasEntityAt<Door>(doorP.X - 1, doorP.Y) && !HasEntityAt<Door>(doorP.X + 1, doorP.Y);

                if (solidLeftAndRight || solidTopAndBottom)
                {
                    if (!haveStartDoor)
                    {
                        startDoor = doorP;
                        haveStartDoor = true;
                    }
                    else
                    {
                        endDoor = doorP;
                        haveEndDoor = true;
                    }
                }
            }

            if (haveStartDoor)
            {
                AddDoor(startDoor, p.doorChance);
            }

            if (haveEndDoor)
            {
                AddDoor(endDoor, p.doorChance);
            }            
        }

        bool IsPassable(int x, int y)
        {
            return !m_Map.BlocksActor(x, y);
        }

        bool IsPassable(Point p)
        {
            return IsPassable(p.X, p.Y);
        }

        string GetTerrainType(int x, int y)
        {
            return m_Map.m_MapData[x, y].TerrainDefinition;
        }

        Type GetEntityType(int x, int y)
        {
            Entity ent = m_Map.GetEntityAt(x, y);
            if (ent != null)
                return ent.GetType();
            return null;
        }

        bool HasEntityAt<T>(Point p)
        {
            return HasEntityAt<T>(p.X, p.Y);
        }

        bool HasEntityAt<T>(int x, int y)
        {
            return GetEntityType(x, y) == typeof(T);
        }

        static Point[] s_8Offsets = {
            new Point(1, 1),
            new Point(1, 0),
            new Point(1, -1),
            new Point(0, 1),
            new Point(0, -1),
            new Point(-1, 1),
            new Point(-1, 0),
            new Point(-1, -1),
        };
        IEnumerable<Point> Get8Neighbors(int x, int y)
        {
            foreach (Point p in s_8Offsets)
                yield return new Point(x + p.X, y + p.Y);
        }

        IEnumerable<Point> Get9Neighbors(int x, int y)
        {
            for (int i = -1; i <= 1; ++i)
                for (int j = -1; j <= 1; ++j)
                    yield return new Point(x + i, y + j);
        }

        IEnumerable<Point> Get25Neighbors(int x, int y)
        {
            for (int i = -2; i <= 2; ++i)
                for (int j = -2; j <= 2; ++j)
                    yield return new Point(x + i, y + j);
        }

        static Point[] s_4Offsets = {
            new Point(1, 0),
            new Point(0, 1),
            new Point(0, -1),
            new Point(-1, 0),
        };
        IEnumerable<Point> Get4Neighbors(int x, int y)
        {
            foreach (Point p in s_4Offsets)
                yield return new Point(x + p.X, y + p.Y);
        }

        int GetNum(Predicate<Point> pred, IEnumerable<Point> points)
        {
            int count = 0;
            foreach (Point p in points)
            {
                if (pred(p))
                    count++;
            }
            return count;
        }
        
        void AddDoor(Point a_p, float a_doorChance)
        {
            if (a_doorChance <= Random.Instance.Next())
                return;

            Door door = new Door("");
            door.Position = a_p;
        }

        void AddDeadEnds(DungeonParams p)
        {
            for (int x = 0; x < m_Map.Width; ++x)
            {
                for (int y = 0; y < m_Map.Height; ++y)
                {
                    if (!IsPassable(x, y))
                        continue;

                    if (p.deadEndChance <= Random.Instance.Next())
                        continue;

                    // bias away from starting inside rooms
                    if (GetNum(IsPassable, Get4Neighbors(x, y)) == 4)
                        continue;

                    Point from = new Point(x, y);
                    int dirX = Random.Instance.Next(2) == 0 ? -1 : 1;
                    int dirY = Random.Instance.Next(2) == 0 ? -1 : 1;
                    Point to = new Point(from.X + dirX * Random.Instance.Next(p.deadEndMinLength, p.deadEndMaxLength),
                                         from.Y + dirY * Random.Instance.Next(p.deadEndMinLength, p.deadEndMaxLength));

                    int maxIters = p.deadEndMaxLength * 2;

                    foreach (Point iter in ScrewyTunnel(m_Map, p.deadEndCorr, from, to, true))
                    {
                        // don't mess up door placement with random tunnels bypassing right next to them
                        if (GetNum(HasEntityAt<Door>, Get8Neighbors(iter.X, iter.Y)) > 0)
                            break;

                        // we hit another tunnel, stop
                        if (GetNum(IsPassable, Get4Neighbors(iter.X, iter.Y)) >= 3)
                            break;

                        SetTerrain(iter.X, iter.Y, "terrain.floor.tilegranite");

                        // screwyTunnels went into an orbit around the target point... it's kind of a bug.
                        maxIters--;
                        if (maxIters == 0)
                            break;
                    }
                }
            }
        }

        void AddEntities(DungeonParams p)
        {
            if (_rooms.Count == 0)
                return;

            // the player starts in a random room (room zero)
            Room heroRoom = _rooms[0];
            Entity hero = m_Map.GetHero();
            hero.Position = heroRoom.RandomPoint();

            // take the furthest room of the first 5 (since they're in random order, we try a few)
            Room stairsRoom = heroRoom;
            int numRoomsToCheck = 5;
            foreach (Room r in _rooms)
            {
                if (numRoomsToCheck == 0)
                    break;
                numRoomsToCheck--;

                if (DistanceSq(heroRoom, r) > DistanceSq(heroRoom, stairsRoom))
                    stairsRoom = r;
            }

            // on the last level of the dungeon, the stairs back up don't appear until you kill the king
            king = PlaceGoblins(p, stairsRoom._Bounds.Center);
            if (king != null)
            {
                king.OnDeath += new Entity.DeathHandler(king_OnDeath);
            }
            else
            {
                PlaceStairs(stairsRoom.RandomPoint());
            }
        }

        Goblin king = null;

        void king_OnDeath(Entity.DeathArgs e)
        {
            PlaceStairs(king.Position);
        }

        void PlaceStairs(Point where)
        {
            // pick a random spot in that room with nothing in it
            // TODO: pick a new room if it's full, or remove the entity?
            for (int i = 0; i < 10; ++i)
            {
                Point randPos = FindFreeSpot(where, 5);
                if (m_Map.GetEntityAt(randPos.X, randPos.Y) != null)
                    continue;

                Stairs stairs = new Stairs();
                stairs.Position = randPos;

                stairs.OnPlayerBump += new Entity.PlayerBumpHandler(Mission.stairs_OnPlayerBump);
                stairs.OnPlayerBump += new Entity.PlayerBumpHandler(stairs_OnPlayerBump);

                break;
            }
        }
            

        private Goblin PlaceGoblins(DungeonParams p, Point start)
        {
            int d = 15;
            if (m_Map.CurrentDepth == 3)
            {
                Goblin gob = new KingGoblin("King Goblin");
                gob.Position = FindFreeSpot(start, d);
                start = gob.Position;
                gob.NextThink = Random.Instance.Next(50) + Timeline.Instance.CurrentTime;
                Timeline.Instance.Add(gob);

                return gob;
            }
            
            int numGobs = (int) (p.goblinDensity * p.height * p.width);
            for (int g = 0; g < numGobs; ++g)
            {
                Goblin gob = new Goblin();
                gob.Position = FindFreeSpot(start, d);
                start = gob.Position;
                gob.NextThink = Random.Instance.Next(50) + Timeline.Instance.CurrentTime;
                Timeline.Instance.Add(gob);
            }

            return null;
        }

    }
}

